#include<stdio.h>
#include<malloc.h>
#define MAX_SIZE 10

int partition(int *, int, int);

int quicksort(int *, int, int);


int main(){
	int *array, i;

	array = (int *)malloc(sizeof(int)*MAX_SIZE);
	printf("QuickSort on Arrays\n");
	for(i=0;i<MAX_SIZE;i++){
		printf("Enter value#%d: ", i);
		scanf("%d", (array+i));
		printf("Okay for value#%d!", i);
	}
	
	printf("\nPerforming QuickSort");
	i = quicksort(array, 0, MAX_SIZE - 1);

	if(i){
		for(i=0;i<MAX_SIZE;i++){
			printf("\nValue#%d: %d", i, array[i]);
		}
	}else{
		printf("\nQuickSort Failed!");
	}
	return 0;
}

int quicksort(int *array, int start, int end){
	printf("start:%d and end:%d", start, end);	
	if(start < end){
		int pivot = partition(array, start, end);
		quicksort(array, start, pivot - 1);
		quicksort(array, pivot + 1, end);
	}else{
		return 0;
	}
	return 1;
}

int partition(int *array, int start, int end){
	int pivot = array[start], i=start+1, j=end, temp;
	printf("\nPivot is: %dth(%d)", start, array[start]);
	while (i < j){
		while(array[i] <= pivot)
			i++;
		while(array[j] > pivot)
			j--;

	//swap the two
		printf("\nSwapping %dth(%d) and %dth(%d).", i, array[i], j, array[j]);
		if(i < j){
			temp = array[i];
			array[i] = array[j];
			array[j] = temp;
		}
	}
	//swap the start and the j	
	array[start] = array[j];
	array[j] = pivot;
	return j;
}
